The present invention relates generally to the fields of distributed computing and Internet-based applications and services. More particularly, the invention relates to methods, apparatus and articles-of-manufactures relating to the collection, organization, maintenance, management and commercial exploitation of network-connected, distributed computing resources.
Distributed (or parallel) computing is a well-established field. Over the past few decades, thousands of distributed computing architectures have been proposed, and hundreds gave been constructed and evaluated.
Distributed computing architectures are typically characterized as being either xe2x80x9ccoarse-grainedxe2x80x9d or xe2x80x9cfine-grained,xe2x80x9d depending upon the size or complexity of the individual processing elements (or xe2x80x9cnodesxe2x80x9d) that perform the computational work. In a typical coarse-grained, distributed computing architecture, the individual processing elements are generally fully functional computing elements, such as single-chip microprocessors, capable of individually performing a variety of useful tasks. The fine-grained approach, by contrast, typically relies on a large number of processing elements, each of which has very limited computational capabilities.
Perhaps the best known fine-grained parallel architecture is The Connection Machine, manufactured by the now-defunct Thinking Machines Corporation. In The Connection Machine, thousands of very-simple processing elements were connected by a highly-efficient message-routing network. Even though individual processing elements lacked the ability to perform much useful on their own, the efficiency of the message-routing network made it possible to cooperatively deploy large numbers of processing elements, on certain problems.
Unlike The Connection Machine, coarse-grained parallel computing systems seldom have the luxury of communication networks that operate with latencies at, or near, the clock speed of individual processing elements. The more sophisticated processing elements used in a coarse-grained distributed processing systems typically cannot be packed into a small volume, like a single chip, board or chassis. As a result, communications must travel across chip-to-chip, board-to-board, or even chassis-to-chassis boundaries, as well as greater physical distances, all of which causes inherent and unavoidable increases in latency. Because of these inherent communication limitations, coarse-grained parallel architectures have, for many years, been viewed by persons skilled in the art as useful only for xe2x80x9ccomputationally intensivexe2x80x9dxe2x80x94as opposed to xe2x80x9ccommunication intensivexe2x80x9dxe2x80x94tasks. A typical computationally intensive task is prime factorization of large integers.
Recently, there have been several efforts to exploit the resources of the world""s largest coarse-grained distributed computing systemxe2x80x94the Internet. The thrust of these efforts has been to apply traditional coarse-grained distributed processing approaches to utilize idle processing resources connected to the World-Wide Web (xe2x80x9cwwwxe2x80x9d). The first reported application of these www-based methods was signal analysis, as part of a search for extra-terrestrial intelligence (xe2x80x9cSETIxe2x80x9d). Several years later, a group at the University of California, Santa Barbara, described the use of web-based distributed parallelism for prime factorization, and other computationally intensive problems. Both of these reported prior-art efforts clearly embrace and exemplify traditional, coarse-grained parallelism thinking, namely, that such parallelism is only useful for computationally intensive, as opposed to communication intensive, problems. See G. Moritz, SETI and Distributed Computing, www.people.fas.harvard.edu/{tilde over ( )}gmoritz/papers/s7.html (1998) (xe2x80x9cDistributed computing is well suited to the search for extraterrestrial civilizations for several reasons. First, the problem itself consists of small blocks of data which each require a large amount of processing. Since CPU time, not bandwidth, is the major requirement of the SERENDIP data analysis, distributed computing via the Internet will be very feasiblexe2x80x9d); A. D. Alexandrov, SuperWeb: Towards a Global Web-Based Parallel Computing Infrastructure, citeseer.nj.nec.com/cachedpage/80115 (1997), at 1 (xe2x80x9cWe expect this approach to work well for non-communication intensive applications, such as prime number factorization, Monte-Carlo and coarse-grained simulations, and othersxe2x80x9d).
The explosive growth of the Web over the past few years has created a huge demand for high-performance, web-centric computing services. Today, such services are typically rendered using mainframe computers (or other high-performance servers), connected to the Web via a T1 line (operating at 1.544 Mb/s). Unfortunately, T1 connectivity is very costly.
At the same time, consumers are increasingly migrating toward high-bandwidth, always-on Web connections, such as those offered by DSL and cable-modem providers. The inventors herein have observed that, as consumer connections to the Internet get faster and cheaper, the ratio of bandwidth-to-cost is far more favorable in the consumer (e.g., DSL and cable-modem) market than in the high-performance corporate (e.g., T1) market. In other words, even at the present time, individuals with high-speed Internet connections are paying far less per unit of bandwidth than high-demand corporate users of T1 lines. Moreover, economies of scale are likely to further drive-down the cost of mass-marketed, high-speed Internet connections, thus making the existing cost disparity even greater.
Accordingly, it would be highly desirable if users of high-performance, web-centric computing services could take advantage of the increasingly cheaper, high-speed, mass-marketed Internet connection services. It would also be highly desirable if such users could take advantage of the millions of often-idle computing resources (e.g., PCs, workstations and other devices) linked to the Internet through such always-on, high-speed, mass-marketed connections. Finally, it would be highly-desirable if owners of such often-idle computing resources could be compensated for use of their resource"" always-on, high-speed Internet connections during otherwise idle periods of time. The invention, as described below, satisfies these and other needs.
In light of the above, one object of the present invention relates to software infrastructure designed to capture a generalized problem-solving capability, handle data throughputs in excess of 100xc3x97 the productivity of the SETI effort, require no access to a worker""s local disk drive (to assuage security concerns) and motivate retail Internet users to participate by paying them in cash or higher-value non-monetary compensation (frequent flyer miles, lottery, discounted products/services, etc.).
Another object of the invention relates to a distributed networking software system that enables thousands, potentially scaled to millions, of consumer PCs on the Internet to be networked together to function as a Virtual Super Computer (xe2x80x9cVSCxe2x80x9d).
Another object of the invention relates to a distributed networking software system that enables a xe2x80x9cCPU/bandwidthxe2x80x9d website exchange to be operated, which web site anonymously and securely brokers demand from web-centric applications seeking integrated (i) data processing and/or (ii) high-bandwidth access to the Internet with retail supply of such resources. Such xe2x80x9cbrokeringxe2x80x9d platform aggregates CPU capability at a commercially-significant unit cost advantage versus the equivalent CPU horsepower of a high-end supercomputer, and aggregates Internet bandwidth access at a commercially-significant cost advantage versus T1, T3, or OC3 high-speed connectivity.
Another object of the invention relates to a distributed networking software system that enables on-demand computing power, with functionality similar to an electric utility, where corporate users can xe2x80x9cplug inxe2x80x9d to the network""s website exchange for powering a wide range of web applications, thereby capitalizing on a distributed problem-solving approach.
Another object of the invention relates to a distributed networking software system that enables flexibility in client deployment, where clients who have unique security concerns or applications which do not require Web integration can licence the software platform for deployment on an intranet or extranet basis only.
In accordance with the invention, the enabling platform is preferably a lightweight overlay that is intended to integrate into virtually any corporate network configuration. Similarly, each retail PC downloads a lightweight installation which invisibly runs in the background and automatically visits a broker website seeking work, whenever the PC""s screensaver is activated.
Another aspect of the invention relates to a multi-tiered server/meta-server architecture configured to support various system management, load balancing, disaster recovery, and security features of the invention.
Another aspect of the invention relates to security. Security is preferably thoroughly integrated into the framework of the invention using a conservative xe2x80x9crestrictedxe2x80x9d approach. Unlike the SETI effort, the invention contemplates use by a variety of parties with potentially conflicting commercial interests; thus, the invention cannot rely on a network of friendly volunteers, and must assume that any one of its retail participants could potentially be hostile in intent.
The invention preferably makes heavy use of security. features available in the Java 2 Platform. The Java Secure Socket Extension (JSSE) and Java Authentication and Authorization Service (JAAS), as well as other Internet-standard cryptography and security APIs provide a rich set of tools to use in connection with the invention. The customer is given flexibility in selecting among different levels of security protection. Preferably, the customer"" code will be xe2x80x9ccloakedxe2x80x9d to protect it from decompilation attacks, and signed using private key and predetermined certificate authority (xe2x80x9cCAxe2x80x9d). In addition, lightweight messages between the customer and servers/brokers will be encrypted. These messages may contain the disguised locations of Java instruction code and data inputs. In turn, these heavyweight items are then also authenticated. Result data is preferably signed by the client program, and server/broker acts as the CA for the worker and customer relationships, and the server/broker preferably only accepts completed work from registered workers who have their private keys registered with the system.
Accordingly, generally speaking, and without intending to be limiting, one aspect of the invention relates to a method for performing distributed, bandwidth-intensive computational tasks, comprising: providing Internet access to at least one broker processor, the at least one broker processor configured to receive jobs from Internet-connected customers; receiving a job from a customer via the Internet; in response to receipt of the job from the customer, directing a plurality of Internet-connected worker-processors to perform a plurality of worker tasks related to the received job; awaiting execution of the worker tasks, the execution characterized by a predominance of worker processor-Internet communication activity; and, upon completion of the execution, confirming the completion of the execution via the Internet. During execution, the plurality of worker processors are preferably collectively utilizing, on average, at least 25% of their total available communication bandwidth, and possibly as much as 30%, 35%, 40%, 50%, 60%, 70% or more. At least part of a worker""s execution may include: (i) searching the Internet in accordance with a search query supplied by the customer; (ii) creating an index; (iii) creating a database; (iv) updating a database; (v) creating a report; (vi) creating a backup or archival file; (vii) performing software maintenance operations; comparing objects downloaded from the Internet; (viii) processing signals or images downloaded from the Internet; (ix) broadcasting audio and/or video to a plurality of destinations on the Internet; and/or sending e-mail to a plurality of destinations on the Internet.
Again, generally speaking, and without intending to be limiting, another aspect of the invention relates to a method for reducing the cost of performing a bandwidth-intensive job on the Internet, the method comprising: (i) transmitting a job execution request to a broker processor over the Internet; (ii) selecting, in response to the job execution request, a plurality of Internet-connected worker processors to be used in executing the job, the selection of worker processors being performed, at least in part, based on one or more bandwidth-related consideration(s); and (iii) using the selected worker processors to execute, at least in part, the job. The worker processor selection is preferably based, at least in part, on one or more bandwidth-related consideration selected from the list of: (i) the types of Internet connections-installed on candidate worker processors; (ii) the locations of candidate worker processors; (iii) the time of day; and (iv) historical performance statistics of candidate worker processors.
Again, generally speaking, and withoutt intending to be limiting, another aspect of the invention relates to a method for exploiting unused computational resources on the Internet, comprising: (i) recruiting prospective worker processors over the Internet, the recruiting including: (a) providing Internet-accessible instructions; (b) providing Internet-downloadable worker processor software; (c) providing an Internet-accessible worker processor operating agreement; and (d) storing a plurality of work processor preferences; (ii) maintaining a registry of worker processors, the maintaining including: (a) storing a plurality of URLs used to address the worker processors; (b) storing a plurality of worker processor profiles, the profiles including information related to hardware and software configurations of the worker processors; and (c) storing a plurality of worker processor past performance metrics; (iii) selecting a plurality of worker processors to collectively execute a job, the selecting being based, at least in part, on worker processor past performance metrics maintained by the worker processor registry; and (iv) using the selected plurality of worker processors to execute the job. At least some of the prospective worker processors may be connected to the Internet via a satellite connection, a fixed wireless connection, and/or a mobile wireless connection. Recruiting prospective worker processors may further include specifying the type and amount of compensation to be provided in exchange for use of worker processor resources, and/or providing an on-line means of accepting the worker processor operating agreement. Maintaining a registry of worker processors may further include determining the performance of worker processors listed in the registry by executing one or more benchmark programs on the worker processors, and optionally updating the worker processor past performance metrics in accordance with measured benchmark program performance statistics. Selecting may be further based, at least in part, on one or more bandwidth-related consideration(s) selected from the list of: (i) the types of Internet connections installed on the worker processors; (ii) the locations of the worker processors; (iii) the time of day; and (iv) one or more of the stored preferences.
Again, generally speaking, and without intending to be limiting, another aspect of the invention relates to a method for reselling Internet bandwidth associated with individual DSL-connected Internet workstations, the method comprising: (i) entering on-line-completed operating agreements with a plurality of DSL-connected Internet users, the agreements providing for use of a plurality of DSL-connected Internet workstations controlled by the users; (ii) executing a customers""s distributed task, using a plurality of the DSL-connected Internet workstations; (iii) storing, for each of the DSL-connected Internet workstations used in the distributed task execution, a bandwidth utilization metric; (iv) compensating the DSL-connected Internet users whose workstations where used in the distributed task execution, the compensation being determined, at least in part, based upon the bandwidth utilization metrics associated with the workstations used in the distributed task execution; and (v) charging the customer whose distributed task was executed using the DSL-connected Internet workstations. The customer is preferably charged, at least in part, based upon the bandwidth utilization metrics associated with the workstations used in executing the customer""s distributed task. Executing a customer""s distributed task may include: (i) receiving an execution request message from the customer over the Internet; (ii) processing the execution request using an Internet-connected broker processor; and (iii) initiating distributed execution of the task by sending messages, over the Internet, to a plurality of the DSL-connected Internet workstations. The compensation is preferably determined, at least in part, by one or more metric(s) selected from the list consisting of: (i) the amount of real time used by the DSL-connected Internet workstations in executing the distributed task; (ii) the amount of processor time used by the DSL-connected Internet workstations in the executing the distributed task; (iii) the amount of primary storage used by the DSL-connected Internet workstation in the executing the distributed task; (iv) the amount of secondary storage used by the DSL-connected Internet workstation in executing the distributed task; (v) the time of day during which the execution occurred; and (vi) the geographic location(s) of the DSL-connected Internet workstations. The plurality of DSL-connected Internet workstations may operate in accordance with any one of the following protocols: ADSL, HDSL, IDSL, MSDSL, RADSL, SDSL, and VDSL (or other similar, or future, protocols).
Again, generally speaking, and without intending to be limiting, another aspect of the invention relates to a method for reselling Internet bandwidth associated with individual cable modem-connected Internet workstations, the method comprising: (i) enrolling a plurality of cable modem-connected Internet users by installing worker processor software on a plurality of cable modem-connected Internet workstations controlled by the users; (ii) using the installed worker processor software to execute a distributed task on a plurality of the cable modem-connected Internet workstations; (iii) using the installed worker processor software to compute, for each workstation used in the distributed task execution, a billing metric determined, at least in part, by the amount of data communication involved in executing the distributed task; (iv) compensating the cable modem-connected Internet-users whose workstations where used in the distributed task execution; (v) charging a customer who requested execution of the distributed task; and (vi) wherein the compensating and charging are performed, at least in part, using one or more of the computed billing metric(s), and wherein, for each distributed task executed, the amount charged to the customer exceeds the sum of all amounts paid to the cable modem-connected Internet users.
Again, generally speaking, and without intending to be limiting, another aspect of the invention relates to a method for executing jobs, comprised of a plurality of tasks, in a networked computing environment, the method comprising: (i) providing networked access to at least one broker processor, the broker processor configured to receive a job from a user, unpack the job into a plurality of executable tasks, and direct a plurality of worker processors to initiate execution of the tasks; (ii) maintaining performance metrics for worker processors; (iii) monitoring completion of tasks by the worker processors and, upon completion, updating the performance metrics; (iv) using the performance metrics to select, at least in part, worker processors to initiate execution of additional tasks; and (v) using the performance metrics to determine, at least in part, the charges to be billed to the user for execution of the job. The method may further include (a) using said performance metrics to detect aberrant performance of worker processors executing tasks; and (b) terminating execution of tasks on worker processors that display aberrant performance.
Further aspects of the invention relate to detection of aberrant worker processor performance, and to use of such detected aberrant performance in maintaining system security and integrity in a distributed processing environment. Worker processor performance metrics may be used to detect aberrant performance by processors executing tasks. In other words, if a processor is expected to complete a task in 1 minute, and the task is not competed in 2 minutes, one may conclude that the processor is (or may be) exhibiting aberrant performance. Another way to detect aberrant performance is to compare the performance of multiple worker processors executing similar tasks. In other words, when similar processors spend significantly different amounts of time (either real time or CPU time) executing similar jobs, it may be concluded that those significantly slower processors are exhibiting some sort of aberrant performance. Because aberrant performance may suggest a security breach on the aberrant-performing worker processor(s), such processor(s) may be selectively disabled and precluded from receiving further task allocations.
Additional aspects of the invention relate to systems, structures and articles-of-manufacture used, or useful, in connection with all, or part, of the above-described methods.
Still further aspects of the invention relate to different combinations or subcombinations of the above-described elements and features in accordance with the teachings of the instant invention.